# -*- coding:utf-8 -*-
"""
Created on Apr 28, 2011

@author: Lithuanian
"""
#########################################
##                                     ##
##   Anytime Graph Search Algorithms   ##
##                                     ##
#########################################


from algorithm import SearchAlgorithm
from graph import Node
from utils import *
from time import time 

class AnytimeGraphSearch (SearchAlgorithm):
    
    #if running experiments - set max run time per problem
    #if not running experiments - set it to None
    EXPERIMENT_MAX_TIME = 90
    
    def __init__(self, container_generator, max_depth=infinity):
        self.container_generator = container_generator
        self.max_depth = max_depth

    def find(self, problem_state, heuristic=None, maxTime = None, open = None, close = None):        
        if not open is None:
            open_states = open
        else:
            open_states = self.container_generator()
            open_states.append(Node(problem_state))
        if close is None:
            closed_states = {}
        else:
            closed_states = close
        solution = None
        start = time()
        while open_states and len(open_states) > 0:
            localTime = time()
            timePassed = localTime - start 
#            print "passed: " + str(timePassed) + " max: " + str(maxTime)            
            if not maxTime is None:
                if timePassed > maxTime:
                    break
            
            #if running experiments - check that runtime is not bigger than the maximal allowed 
            #experiment run time
            if not self.EXPERIMENT_MAX_TIME is None:
                if timePassed > self.EXPERIMENT_MAX_TIME:
                    return solution
                
            node = open_states.pop()

            #some trimming....             
            if not solution is None:
                #if path to current node is bigger than the path to the known solution - a better
                #solution can not be derived from this node
                if len(node.getPathActions()) >= len(solution.getPathActions()):
                    continue
                #a better solution is possible only if the path to the current node + best possible solution is
                #not worse than the solution we already have 
                if len(node.getPathActions()) \
                    + optimisticEvaluation(node.state.dirt_locations, node.state.robots) > len(solution.getPathActions()):
                    continue

            if node.depth > self.max_depth:
                continue
            
            #not anytime behaviour - return first solution!
            if maxTime is None and node.state.isGoal():
                return node.getPathActions()
            
            #check if goal state            
            if node.state.isGoal() and (solution is None or len(node.getPathActions()) < len(solution.getPathActions())):
                solution = node
#                print "+New Solution! Value: ", len(solution.getPathActions())
                continue
            
            if (not node.state in closed_states) or (node.path_cost < closed_states[node.state]):
                closed_states[node.state] = node.path_cost
                open_states.extend(node.expand())
            
        if solution is None:
            return None
        if solution.state.isGoal():
            return solution.getPathActions()
        return None
   
#############################################
##                                         ##
##   Anytime Best-First Search Algorithm   ##
##                                         ##
#############################################

# This is an implementation of the SearchAlgorithm interface for the following
# search algorithms:
# - BestFirstGraphSearch

from algorithm import SearchAlgorithm

class AnytimeBestFirstGraphSearch (SearchAlgorithm):
    def __init__(self, max_depth=infinity):
        self.max_depth = max_depth

    def find(self, problem_state, heuristic, time, open = None, closed = {}):
        # This is the node evaluation function for the given heuristic.
        def evaluator(node):
            return heuristic.evaluate(node.state)
            
        # This is a generator for the PriorityQueue we need.
        def queue_generator():
            return PriorityQueue(evaluator)
 
        # Use a graph search with a minimum priority queue to conduct the search.
        search = AnytimeGraphSearch(queue_generator, self.max_depth)
        if open is None:
            return search.find(problem_state,heuristic, time)
        return search.find(problem_state,heuristic, time, open, closed)
    
class AnytimeAstarGraphSearch(SearchAlgorithm):
    def __init__(self, phase, max_depth=infinity):
        self.max_depth = max_depth
        self.phase = phase
    
    def find(self, problem_state, heuristic=None, maxTime = None, phase = None):
        '''
        Performs a full graph search, expanding the nodes on the fringe into
        the queue given at construction time, and then goes through those nodes
        at the order of the queue.
        If a maximal depth was provided at construction, the search will not
        pursue nodes that are more than that depth away in distance from the
        initial state.
                
        @param problem_state: The initial state to start the search from.
        @param heuristic: Ignored.
        '''
        # This is the node evaluation function for the given heuristic.
        def evaluator(node):
            return node.path_cost + heuristic.evaluate(node.state)
        
        if phase is None:
            phase = self.phase

        open_states = PriorityQueue(evaluator)
        open_states.append(Node(problem_state))
        closed_states = {}
        solution = None
        start = time()
        
        while open_states and len(open_states) > 0:
            localTime = time()
            if localTime - start > phase*maxTime:
                anyTimeBF = AnytimeRandRestBF()
                return anyTimeBF.find(None, heuristic, maxTime - (localTime - start),\
                                      open_states, closed_states)
            
            #just in case...
            if localTime - start > maxTime:
                return solution.getPathActions()
            
            node = open_states.pop()
            
            if node.depth > self.max_depth:
                continue
            
            if node.state.isGoal(): 
                if solution is None or len(solution.getPathActions()) > len(node.getPathActions()):
                        solution = node
                closed_states[node.state] = node.path_cost
                continue
            
            #some trimming....
            if not solution is None:
                #if path to current node is bigger than the path to the known solution - a better
                #solution can not be derived from this node
                if len(node.getPathActions()) >= len(solution.getPathActions()):
                    closed_states[node.state] = node.path_cost
                    continue
                #a better solution is possible only if the path to the current node + best possible solution is
                #not worse than the solution we already have 
                if len(node.getPathActions()) \
                    + optimisticEvaluation(node.state.dirt_locations, node.state.robots) > len(solution.getPathActions()):
                    closed_states[node.state] = node.path_cost
                    continue
            
            if (node.state not in closed_states) or (node.path_cost < closed_states[node.state]):
                closed_states[node.state] = node.path_cost
                open_states.extend(node.expand())
                
        return None

def optimisticEvaluation(piles, robots):
            '''
            calculate distance to the closest pile (without obstacles) => the 
            best possible solution will be >= calculated distance
            '''
            absuluteMinPath = None
            for pile in piles:
                minPathToPile = None
                for robot in robots:
                    dest = abs(robot[0] - pile[0]) + abs(robot[1] - pile[1])
                    if minPathToPile is None:
                        minPathToPile = dest
                        continue
                    if dest < minPathToPile:
                        minPathToPile = dest
                if absuluteMinPath is None or absuluteMinPath > minPathToPile:
                    absuluteMinPath = minPathToPile
            if absuluteMinPath is None:
                return 0
            return absuluteMinPath
#----------------------------------------------------------------------
class AnytimeRandRestBF(SearchAlgorithm):
    
    #if running experiments - set max run time per problem
    #if not running experiments - set it to None
    EXPERIMENT_MAX_TIME = 120
    
    def __init__(self, max_depth=infinity):
        self.max_depth = max_depth

    def find(self, problem_state, heuristic=None, maxTime = None, open = None, close = None):    
        def evaluator(node):
            val = heuristic.evaluate(node.state)
            return val
            
        # This is a generator for the PriorityQueue we need.
        def queue_generator():
            return PriorityQueue(evaluator)
                
        if not open is None:
            open_states = open
        else:
            open_states = queue_generator()
            open_states.append(Node(problem_state))
        if close is None:
            closed_states = {}
        else:
            closed_states = close
        solution = None
        start = time()
        while open_states and len(open_states) > 0:
            localTime = time()
            timePassed = localTime - start             
            if not maxTime is None:
                if timePassed > maxTime:
                    break
            
#            #if running experiments - check that runtime is not bigger than the maximal allowed 
#            #experiment run time
#            if not self.EXPERIMENT_MAX_TIME is None:
#                if timePassed > self.EXPERIMENT_MAX_TIME:
#                    return solution
            
            node = open_states.pop()                

            #some trimming....             
            if not solution is None:
                #if path to current node is bigger than the path to the known solution - a better
                #solution can not be derived from this node
                if len(node.getPathActions()) >= len(solution.getPathActions()):
                    closed_states[node.state] = node.path_cost
                    continue
                #a better solution is possible only if the path to the current node + best possible solution is
                #not worse than the solution we already have 
                if len(node.getPathActions()) \
                    + optimisticEvaluation(node.state.dirt_locations, node.state.robots) >= len(solution.getPathActions()):
                    closed_states[node.state] = node.path_cost
                    continue

            if node.depth > self.max_depth:
                continue
            
            #not anytime behaviour - return first solution!
#            if maxTime is None and node.state.isGoal():
#                return node.getPathActions()
            
            #check if goal state            
            if node.state.isGoal() and (solution is None or len(node.getPathActions()) < len(solution.getPathActions())):
                solution = node
                closed_states[node.state] = node.path_cost
                continue
            
            if (not node.state in closed_states) or (node.path_cost < closed_states[node.state]):
                closed_states[node.state] = node.path_cost
                open_states.extend(node.expand())
                
            timePassed = localTime - start             
            if not maxTime is None:
                if timePassed > maxTime:
                    break                
            
        if solution is None:
            return None
        if solution.state.isGoal():
            return solution.getPathActions()
        return None